Session 21. Random Forests: Bagging, Out-Of-Bag (OOB) Error, Bootstrap Samples + Random Subspace Method.

Feedback should be send to goran.milovanovic@datakolektiv.com. These notebooks accompany the Intro to Data Science: Non-Technical Background course 2020/21.


What do we want to do today?

Today we will introduce an idea even more powerful than the Decision Tree model to solve classification and regression problems: the Random Forest model. We will rely on the R package {randomForest} to train Random Forests in both classification and regression contexts. In order to understand Random Forests we will introduce some important theoretical concepts: Bootstrap aggregating (a.k.a. Bagging), Out-of-bag (OOB) error, and Feature Bagging (a.k.a. the random subspace method or attribute bagging). We will see how these approaches in Machine Learning prevent overfitting in the training of a complex model like Random Forest.

0. Setup

install.packages('randomForest')
install.packages('glmnet')

Grab the HR_comma_sep.csv dataset from the Kaggle and place it in your _data directory for this session. We will also use the Boston Housing Dataset: BostonHousing.csv

dataDir <- paste0(getwd(), "/_data/")
library(tidyverse)
library(data.table)
library(randomForest)
library(ggrepel)

1. Random Forests for Classification

We begin by loading and inspecting the HR_comma_sep.csv dataset:

dataSet <- read.csv(paste0(getwd(), "/_data/HR_comma_sep.csv"),
                    header = T,
                    check.names = 1,
                    stringsAsFactors = F)
glimpse(dataSet)
Rows: 14,999
Columns: 10
$ satisfaction_level    <dbl> 0.38, 0.80, 0.11, 0.72, 0.37, 0.41, 0.10, 0.92, 0.89, 0.42, 0.45, 0.11, 0.84, 0.41, 0.36, 0.38, 0.45, 0.78, 0.45...
$ last_evaluation       <dbl> 0.53, 0.86, 0.88, 0.87, 0.52, 0.50, 0.77, 0.85, 1.00, 0.53, 0.54, 0.81, 0.92, 0.55, 0.56, 0.54, 0.47, 0.99, 0.51...
$ number_project        <int> 2, 5, 7, 5, 2, 2, 6, 5, 5, 2, 2, 6, 4, 2, 2, 2, 2, 4, 2, 5, 6, 2, 6, 2, 2, 5, 4, 2, 2, 2, 6, 2, 2, 2, 4, 6, 2, 2...
$ average_montly_hours  <int> 157, 262, 272, 223, 159, 153, 247, 259, 224, 142, 135, 305, 234, 148, 137, 143, 160, 255, 160, 262, 282, 147, 30...
$ time_spend_company    <int> 3, 6, 4, 5, 3, 3, 4, 5, 5, 3, 3, 4, 5, 3, 3, 3, 3, 6, 3, 5, 4, 3, 4, 3, 3, 5, 5, 3, 3, 3, 4, 3, 3, 3, 6, 4, 3, 3...
$ Work_accident         <int> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0...
$ left                  <int> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1...
$ promotion_last_5years <int> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0...
$ sales                 <chr> "sales", "sales", "sales", "sales", "sales", "sales", "sales", "sales", "sales", "sales", "sales", "sales", "sal...
$ salary                <chr> "low", "medium", "medium", "low", "low", "low", "low", "low", "low", "low", "low", "low", "low", "low", "low", "...

The task is to predict the value of left - whether the employee has left the company or not - from a set of predictors encompassing the following:

  • satisfaction_level: a measure of employee’s level of satisfaction
  • last_evaluation: the result of a last evaluation
  • number_projects: in how many projects did the employee took part
  • average_monthly_hours: how working hours monthly on average
  • time_spend_company: for how long is the employee with us
  • Work_accident: any work accidents?
  • promotion_last_5years: did the promotion occur in the last five years?
  • sales: department (sales, accounting, hr, technical, support, management, IT, product_mng, marketing, RandD)
  • salary: salary class (low, medium, high)

1.1 Random Forests: the Algorithm

There three important concepts to understand how Random Forest builds upon Decision Trees:

  • Bootstrap aggregating (Bagging). We begin with some training set for our model, \(D\). Bagging generates \(m\) new training sets, \(D_i\), \(i = 1, 2, ..., m\), by randomly sampling from \(D\) uniformly and with replacement. The samples obtained in this way are known as bootstrap samples. In Random Forests, \(m\) simpler models - Decision Trees, precisely - are fitted for each \(D_i\) bootstrap sample.

  • Out-of-bag (OOB) error. Each time a new bootstrap sample \(D_i\) is produced, some data points remain out of the bag, are not used in model training, and form the OOB set (the Out-of-bag set). The OOB error is a prediction error (remember this concept from our introduction to cross-validation?) which is computed from the OOB set, where the prediction is obtained by averaging the response (in regression) or as a majority vote (in classification) from all the trees in the forest that were not trained on that particular OOB instance.

  • The Random Subspace Method (Feature Bagging). The Random Subspace Method is a method to control for the complexity of the decision trees grown in a Random Forest model. On each new split, only a randomly chosen subset of predictors is used to find the optimal split. The Random Forests algorithm, as we will see, has a control parameter that determines how many features are randomly selected to produce a new split.

1.2 Classification w. {randomForest}

We will fit a Random Forest model to the HR_comma_sep.csv dataset with randomForest::randomForest() in R. In spite of all the precautionary measures already taken in the Random Forest model itself, we will still perform an additional outter k-fold cross-validation with 5 folds: better safe than sorry.

First, define the folds:

dataSet$ix <- sample(1:5, dim(dataSet)[1], replace = T)
table(dataSet$ix)

   1    2    3    4    5 
3099 2962 2997 2941 3000 

Perform a 5-fold cross validation for a set of Random Forests across the following control parameters:

  • ntree: the number of trees to grow
  • mtry: the number of variables to randomly sample as candidates at each split (to control Feature Bagging)
ntree <- seq(250, 1000, by = 250)
mtry <- 1:(dim(dataSet)[2]-2)
# - mtry: we do not count `left` which is an outcome
# - and `ix` which is a fold index, so we have
# - dim(dataSet)[2]-2 predictors in the model.
# - start timer:
tstart <- Sys.time()
rfModels <- lapply(ntree, function(nt) {
  # - lapply() across ntree
  mtrycv <- lapply(mtry, function(mt) {
    # - lapply() across mt
    cv <- lapply(unique(dataSet$ix), function(fold) {
      # - lapply across folds:
      # - split training and test sets
      testIx <- fold
      trainIx <- setdiff(1:5, testIx)
      trainSet <- dataSet %>% 
        dplyr::filter(ix %in% trainIx) %>% 
        dplyr::select(-ix)
      testSet <- dataSet %>% 
        dplyr::filter(ix %in% testIx) %>%
        dplyr::select(-ix)
      # - `left` to factor for classification 
      # -  w. randomForest()
      trainSet$left <- as.factor(trainSet$left)
      testSet$left <- as.factor(testSet$left)
      # - Random Forest:
      model <- randomForest::randomForest(formula = left ~ .,
                                          data = trainSet, 
                                          ntree = nt,
                                          mtry = mt
                                          )
      # - ROC analysis:
      predictions <- predict(model, 
                             newdata = testSet)
      hit <- sum(ifelse(predictions == 1 & testSet$left == 1, 1, 0))
      hit <- hit/sum(testSet$left == 1)
      fa <- sum(ifelse(predictions == 1 & testSet$left == 0, 1, 0))
      fa <- fa/sum(testSet$left == 0)
      acc <- sum(predictions == testSet$left)
      acc <- acc/length(testSet$left)
      # - Output:
      return(
        data.frame(fold, hit, fa, acc)
      )
    })
    # - collect results from all folds:
    cv <- rbindlist(cv)
    # - average ROC:
    avg_roc <- data.frame(hit = mean(cv$hit),
                          fa = mean(cv$fa), 
                          acc = mean(cv$acc),
                          mtry = mt)
    return(avg_roc)
  })
  # - collect from all mtry values:
  mtrycv <- rbindlist(mtrycv)
  # - add ntree and out:
  mtrycv$ntree <- nt
  return(mtrycv)
})
# - collect all results
rfModels <- rbindlist(rfModels)
write.csv(rfModels, 
          paste0(getwd(), "/rfModels.csv"))
# - Report timing:
print(paste0("The estimation took: ", 
             difftime(Sys.time(), tstart, units = "mins"), 
             " minutes."))
[1] "The estimation took: 18.1753468314807 minutes."
print(rfModels)

Let’s inspect the CV results visually. Accuracy first:

rfModels$ntree <- factor(rfModels$ntree)
rfModels$mtry <- factor(rfModels$mtry)
ggplot(data = rfModels, 
       aes(x = mtry,
           y = acc, 
           group = ntree, 
           color = ntree,
           fill = ntree,
           label = round(acc, 2))
       ) +
  geom_path(size = .25) + 
  geom_point(size = 1.5) + 
  ggtitle("Random Forests CV: Accuracy") +
  theme_bw() + 
  theme(panel.border = element_blank()) +
  theme(plot.title = element_text(hjust = .5, size = 8))

Hit rate:

ggplot(data = rfModels, 
       aes(x = mtry,
           y = hit, 
           group = ntree, 
           color = ntree,
           fill = ntree,
           label = round(acc, 2))
       ) +
  geom_path(size = .25) + 
  geom_point(size = 1.5) + 
  ggtitle("Random Forests CV: Hit Rate") +
  theme_bw() + 
  theme(panel.border = element_blank()) +
  theme(plot.title = element_text(hjust = .5, size = 8))

False Alarm rate:

ggplot(data = rfModels, 
       aes(x = mtry,
           y = fa, 
           group = ntree, 
           color = ntree,
           fill = ntree,
           label = round(acc, 2))
       ) +
  geom_path(size = .25) + 
  geom_point(size = 1.5) + 
  ggtitle("Random Forests CV: FA Rate") +
  theme_bw() + 
  theme(panel.border = element_blank()) +
  theme(plot.title = element_text(hjust = .5, size = 8))

And pick the best model from ROC:

rfModels$diff <- rfModels$hit - rfModels$fa
w_best <- which.max(rfModels$diff)
rfModels[w_best, ]

And we can still refine the chosen model:

dataSet <- dataSet %>% 
  dplyr::select(-ix)
dataSet$left <- factor(dataSet$left)
optimal_model <- randomForest::randomForest(formula = left ~ .,
                                            data = dataSet,
                                            ntree = 250,
                                            mtry = 4)
optimal_model$importance
                      MeanDecreaseGini
satisfaction_level         2058.254674
last_evaluation             638.526242
number_project              897.076403
average_montly_hours        753.194652
time_spend_company          976.836267
Work_accident                16.064299
promotion_last_5years         2.851143
sales                        58.493822
salary                       34.418528

The cumulative OOB error up to the i-th tree can be found in the first column of the optimal_model$err.rate field:

head(optimal_model$err.rate)
            OOB          0          1
[1,] 0.02388389 0.01576522 0.04924242
[2,] 0.02402065 0.01651917 0.04790982
[3,] 0.02308386 0.01634684 0.04456193
[4,] 0.02230216 0.01514036 0.04501501
[5,] 0.01942832 0.01242054 0.04175756
[6,] 0.01923214 0.01231666 0.04118174

Let’s take a closer look at it:

oobFrame <- as.data.frame(optimal_model$err.rate)
oobFrame$ntree <- 1:dim(oobFrame[1])
ggplot(data = oobFrame, 
       aes(x = ntree,
           y = OOB)) + 
  geom_path(size = .25) + 
  geom_point(size = 1.5) + 
  ggtitle("Cumulative OOB error from the CV optimal Random Forest model") +
  theme_bw() + 
  theme(panel.border = element_blank()) +
  theme(plot.title = element_text(hjust = .5, size = 8))

We can observe how the cumulative OOB error stabilizes following the growth of a certain number of trees in the Random Forest model:

w_tree <- which.min(oobFrame$OOB)
print(w_tree)
[1] 198

And finally:

optimal_model <- randomForest::randomForest(formula = left ~ .,
                                            data = dataSet,
                                            ntree = w_tree,
                                            mtry = 4
                                            )
predictions <- predict(optimal_model, 
                       newdata = dataSet)
hit <- sum(ifelse(predictions == 1 & dataSet$left == 1, 1, 0))
hit <- hit/sum(dataSet$left == 1)
fa <- sum(ifelse(predictions == 1 & dataSet$left == 0, 1, 0))
fa <- fa/sum(dataSet$left == 0)
acc <- sum(predictions == dataSet$left)
acc <- acc/length(dataSet$left)
print(paste0("Accuracy: ", acc, "; Hit rate: ", hit, "; FA rate: ", fa))
[1] "Accuracy: 0.999933328888593; Hit rate: 1; FA rate: 8.75043752187609e-05"

2. Random Forests for Regression

In {randomForest}, to obtain the Random Forest model for regression simply do not pronounce an outcome to be a factor. We will use the Boston Housing dataset to demonstrate.

dataSet <- read.csv(paste0('_data/', 'BostonHousing.csv'), 
                    header = T, 
                    check.names = F,
                    stringsAsFactors = F)
head(dataSet)

Here are the variables:

  • crim: per capita crime rate by town
  • zn: proportion of residential land zoned for lots over 25,000 sq.ft.
  • indus: proportion of non-retail business acres per town.
  • chas: Charles River dummy variable (1 if tract bounds river; 0 otherwise)
  • nox: nitric oxides concentration (parts per 10 million)
  • rm: average number of rooms per dwelling
  • age: proportion of owner-occupied units built prior to 1940
  • dis: weighted distances to five Boston employment centers
  • rad: index of accessibility to radial highways
  • tax: full-value property-tax rate per $10,000
  • ptratio: pupil-teacher ratio by town
  • b: 1000(Bk - 0.63)^2 where Bk is the proportion of blacks by town
  • lstat: % lower status of the population
  • medv: Median value of owner-occupied homes in $1000’s

The medv variable is the outcome.

Random Forest (no cross-validation this time):

rfRegMsodel <- randomForest::randomForest(formula = medv ~ .,
                                          data = dataSet,
                                          ntree = 1000,
                                          mtry = 7
                                          )

We can use the generic plot() function to assess how the MSE changes across ntree:

plot(rfRegMsodel)

predictions <- predict(rfRegMsodel, 
                       newdata = dataSet)
predictFrame <- data.frame(predicted_medv = predictions, 
                           observed_medv = dataSet$medv)
ggplot(data = predictFrame, 
       aes(x = predicted_medv,
           y = observed_medv)) + 
  geom_smooth(method = "lm", size = .25, color = "red") + 
  geom_point(size = 1.5, color = "black") + 
  geom_point(size = .75, color = "white") +
  ggtitle("Random Forest in Regression: Observed vs Predicted\nBoston Housing Dataset") + 
  theme_bw() + 
  theme(panel.border = element_blank()) +
  theme(plot.title = element_text(hjust = .5, size = 8))


Further Readings


Goran S. Milovanović

DataKolektiv, 2020/21

contact:


License: GPLv3 This Notebook is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This Notebook is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this Notebook. If not, see http://www.gnu.org/licenses/.


LS0tDQp0aXRsZTogSW50cm8gdG8gRGF0YSBTY2llbmNlIChOb24tVGVjaG5pY2FsIEJhY2tncm91bmQsIFIpIC0gU2Vzc2lvbjIxDQphdXRob3I6DQotIG5hbWU6IEdvcmFuIFMuIE1pbG92YW5vdmnEhywgUGhEDQogIGFmZmlsaWF0aW9uOiBEYXRhS29sZWt0aXYsIENoaWVmIFNjaWVudGlzdCAmIE93bmVyOyBEYXRhIFNjaWVudGlzdCBmb3IgV2lraWRhdGEsIFdNREUNCmFic3RyYWN0OiANCm91dHB1dDoNCiAgaHRtbF9ub3RlYm9vazoNCiAgICBjb2RlX2ZvbGRpbmc6IHNob3cNCiAgICB0aGVtZTogc3BhY2VsYWINCiAgICB0b2M6IHllcw0KICAgIHRvY19mbG9hdDogeWVzDQogICAgdG9jX2RlcHRoOiA1DQogIGh0bWxfZG9jdW1lbnQ6DQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZGVwdGg6IDUNCi0tLQ0KDQohW10oLi4vX2ltZy9ES19Mb2dvXzEwMC5wbmcpDQoNCioqKg0KIyBTZXNzaW9uIDIxLiBSYW5kb20gRm9yZXN0czogQmFnZ2luZywgT3V0LU9mLUJhZyAoT09CKSBFcnJvciwgQm9vdHN0cmFwIFNhbXBsZXMgKyBSYW5kb20gU3Vic3BhY2UgTWV0aG9kLg0KDQoqKkZlZWRiYWNrKiogc2hvdWxkIGJlIHNlbmQgdG8gYGdvcmFuLm1pbG92YW5vdmljQGRhdGFrb2xla3Rpdi5jb21gLiANClRoZXNlIG5vdGVib29rcyBhY2NvbXBhbnkgdGhlIEludHJvIHRvIERhdGEgU2NpZW5jZTogTm9uLVRlY2huaWNhbCBCYWNrZ3JvdW5kIGNvdXJzZSAyMDIwLzIxLg0KDQoqKioNCg0KIyMjIFdoYXQgZG8gd2Ugd2FudCB0byBkbyB0b2RheT8NCg0KVG9kYXkgd2Ugd2lsbCBpbnRyb2R1Y2UgYW4gaWRlYSBldmVuIG1vcmUgcG93ZXJmdWwgdGhhbiB0aGUgRGVjaXNpb24gVHJlZSBtb2RlbCB0byBzb2x2ZSBjbGFzc2lmaWNhdGlvbiBhbmQgcmVncmVzc2lvbiBwcm9ibGVtczogKip0aGUgUmFuZG9tIEZvcmVzdCBtb2RlbCoqLiBXZSB3aWxsIHJlbHkgb24gdGhlIFIgcGFja2FnZSBbe3JhbmRvbUZvcmVzdH1dKGh0dHBzOi8vY3Jhbi5yLXByb2plY3Qub3JnL3dlYi9wYWNrYWdlcy9yYW5kb21Gb3Jlc3QvKSB0byB0cmFpbiBSYW5kb20gRm9yZXN0cyBpbiBib3RoIGNsYXNzaWZpY2F0aW9uIGFuZCByZWdyZXNzaW9uIGNvbnRleHRzLiBJbiBvcmRlciB0byB1bmRlcnN0YW5kIFJhbmRvbSBGb3Jlc3RzIHdlIHdpbGwgaW50cm9kdWNlIHNvbWUgaW1wb3J0YW50IHRoZW9yZXRpY2FsIGNvbmNlcHRzOiAqQm9vdHN0cmFwIGFnZ3JlZ2F0aW5nKiAoYS5rLmEuICpCYWdnaW5nKiksICpPdXQtb2YtYmFnIChPT0IpIGVycm9yKiwgYW5kICpGZWF0dXJlIEJhZ2dpbmcqIChhLmsuYS4gKnRoZSByYW5kb20gc3Vic3BhY2UgbWV0aG9kKiBvciAqYXR0cmlidXRlIGJhZ2dpbmcqKS4gV2Ugd2lsbCBzZWUgaG93IHRoZXNlIGFwcHJvYWNoZXMgaW4gTWFjaGluZSBMZWFybmluZyBwcmV2ZW50IG92ZXJmaXR0aW5nIGluIHRoZSB0cmFpbmluZyBvZiBhIGNvbXBsZXggbW9kZWwgbGlrZSBSYW5kb20gRm9yZXN0Lg0KDQoNCiMjIyAwLiBTZXR1cA0KDQpgYGB7ciBlY2hvID0gVCwgZXZhbCA9IEZ9DQppbnN0YWxsLnBhY2thZ2VzKCdyYW5kb21Gb3Jlc3QnKQ0KaW5zdGFsbC5wYWNrYWdlcygnZ2xtbmV0JykNCmBgYA0KDQpHcmFiIHRoZSBgSFJfY29tbWFfc2VwLmNzdmAgZGF0YXNldCBmcm9tIHRoZSBbS2FnZ2xlXShodHRwczovL3d3dy5rYWdnbGUuY29tL2xpdWppYXFpL2hyLWNvbW1hLXNlcGNzdikgYW5kIHBsYWNlIGl0IGluIHlvdXIgYF9kYXRhYCBkaXJlY3RvcnkgZm9yIHRoaXMgc2Vzc2lvbi4gV2Ugd2lsbCBhbHNvIHVzZSB0aGUgW0Jvc3RvbiBIb3VzaW5nIERhdGFzZXQ6ICBCb3N0b25Ib3VzaW5nLmNzdl0oaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL3NlbHZhODYvZGF0YXNldHMvbWFzdGVyL0Jvc3RvbkhvdXNpbmcuY3N2KQ0KDQpgYGB7ciBlY2hvID0gVCwgbWVzc2FnZSA9IEYsIHdhcm5pbmcgPSBGfQ0KZGF0YURpciA8LSBwYXN0ZTAoZ2V0d2QoKSwgIi9fZGF0YS8iKQ0KbGlicmFyeSh0aWR5dmVyc2UpDQpsaWJyYXJ5KGRhdGEudGFibGUpDQpsaWJyYXJ5KHJhbmRvbUZvcmVzdCkNCmxpYnJhcnkoZ2dyZXBlbCkNCmBgYA0KDQoNCiMjIyAxLiBSYW5kb20gRm9yZXN0cyBmb3IgQ2xhc3NpZmljYXRpb24NCg0KV2UgYmVnaW4gYnkgbG9hZGluZyBhbmQgaW5zcGVjdGluZyB0aGUgYEhSX2NvbW1hX3NlcC5jc3ZgIGRhdGFzZXQ6DQoNCmBgYHtyIGVjaG8gPSBULCBtZXNzYWdlID0gRiwgd2FybmluZyA9IEZ9DQpkYXRhU2V0IDwtIHJlYWQuY3N2KHBhc3RlMChnZXR3ZCgpLCAiL19kYXRhL0hSX2NvbW1hX3NlcC5jc3YiKSwNCiAgICAgICAgICAgICAgICAgICAgaGVhZGVyID0gVCwNCiAgICAgICAgICAgICAgICAgICAgY2hlY2submFtZXMgPSAxLA0KICAgICAgICAgICAgICAgICAgICBzdHJpbmdzQXNGYWN0b3JzID0gRikNCmdsaW1wc2UoZGF0YVNldCkNCmBgYA0KVGhlIHRhc2sgaXMgdG8gcHJlZGljdCB0aGUgdmFsdWUgb2YgYGxlZnRgIC0gd2hldGhlciB0aGUgZW1wbG95ZWUgaGFzIGxlZnQgdGhlIGNvbXBhbnkgb3Igbm90IC0gZnJvbSBhIHNldCBvZiBwcmVkaWN0b3JzIGVuY29tcGFzc2luZyB0aGUgZm9sbG93aW5nOg0KDQotICoqc2F0aXNmYWN0aW9uX2xldmVsKio6IGEgbWVhc3VyZSBvZiBlbXBsb3llZSdzIGxldmVsIG9mIHNhdGlzZmFjdGlvbg0KLSAqKmxhc3RfZXZhbHVhdGlvbioqOiB0aGUgcmVzdWx0IG9mIGEgbGFzdCBldmFsdWF0aW9uDQotICoqbnVtYmVyX3Byb2plY3RzKio6IGluIGhvdyBtYW55IHByb2plY3RzIGRpZCB0aGUgZW1wbG95ZWUgdG9vayBwYXJ0DQotICoqYXZlcmFnZV9tb250aGx5X2hvdXJzKio6IGhvdyB3b3JraW5nIGhvdXJzIG1vbnRobHkgb24gYXZlcmFnZQ0KLSAqKnRpbWVfc3BlbmRfY29tcGFueSoqOiBmb3IgaG93IGxvbmcgaXMgdGhlIGVtcGxveWVlIHdpdGggdXMNCi0gKipXb3JrX2FjY2lkZW50Kio6IGFueSB3b3JrIGFjY2lkZW50cz8NCi0gKipwcm9tb3Rpb25fbGFzdF81eWVhcnMqKjogZGlkIHRoZSBwcm9tb3Rpb24gb2NjdXIgaW4gdGhlIGxhc3QgZml2ZSB5ZWFycz8NCi0gKipzYWxlcyoqOiBkZXBhcnRtZW50IChzYWxlcywgYWNjb3VudGluZywgaHIsIHRlY2huaWNhbCwgc3VwcG9ydCwgbWFuYWdlbWVudCwgSVQsIHByb2R1Y3RfbW5nLCBtYXJrZXRpbmcsIFJhbmREKQ0KLSAqKnNhbGFyeSoqOiBzYWxhcnkgY2xhc3MgKGxvdywgbWVkaXVtLCBoaWdoKQ0KDQoNCiMjIyMgMS4xIFJhbmRvbSBGb3Jlc3RzOiB0aGUgQWxnb3JpdGhtDQoNClRoZXJlIHRocmVlIGltcG9ydGFudCBjb25jZXB0cyB0byB1bmRlcnN0YW5kIGhvdyBSYW5kb20gRm9yZXN0IGJ1aWxkcyB1cG9uIERlY2lzaW9uIFRyZWVzOg0KDQohW10oLi4vX2ltZy9TMjFfMDFfUmFuZG9tRm9yZXN0LmpwZWcpDQoNCi0gKipCb290c3RyYXAgYWdncmVnYXRpbmcgKEJhZ2dpbmcpLioqIFdlIGJlZ2luIHdpdGggc29tZSB0cmFpbmluZyBzZXQgZm9yIG91ciBtb2RlbCwgJEQkLiBCYWdnaW5nIGdlbmVyYXRlcyAkbSQgbmV3IHRyYWluaW5nIHNldHMsICREX2kkLCAkaSA9IDEsIDIsIC4uLiwgbSQsIGJ5IHJhbmRvbWx5IHNhbXBsaW5nIGZyb20gJEQkIHVuaWZvcm1seSBhbmQgKndpdGggcmVwbGFjZW1lbnQqLiBUaGUgc2FtcGxlcyBvYnRhaW5lZCBpbiB0aGlzIHdheSBhcmUga25vd24gYXMgKmJvb3RzdHJhcCBzYW1wbGVzKi4gSW4gUmFuZG9tIEZvcmVzdHMsICRtJCBzaW1wbGVyIG1vZGVscyAtIERlY2lzaW9uIFRyZWVzLCBwcmVjaXNlbHkgLSBhcmUgZml0dGVkIGZvciBlYWNoICREX2kkIGJvb3RzdHJhcCBzYW1wbGUuIA0KDQotICoqT3V0LW9mLWJhZyAoT09CKSBlcnJvci4qKiBFYWNoIHRpbWUgYSBuZXcgYm9vdHN0cmFwIHNhbXBsZSAkRF9pJCBpcyBwcm9kdWNlZCwgc29tZSBkYXRhIHBvaW50cyByZW1haW4gKm91dCBvZiB0aGUgYmFnKiwgYXJlIG5vdCB1c2VkIGluIG1vZGVsIHRyYWluaW5nLCBhbmQgZm9ybSB0aGUgKipPT0Igc2V0KiogKHRoZSAqT3V0LW9mLWJhZyBzZXQqKS4gVGhlIE9PQiBlcnJvciBpcyBhICpwcmVkaWN0aW9uIGVycm9yKiAocmVtZW1iZXIgdGhpcyBjb25jZXB0IGZyb20gb3VyIGludHJvZHVjdGlvbiB0byBjcm9zcy12YWxpZGF0aW9uPykgd2hpY2ggaXMgY29tcHV0ZWQgZnJvbSB0aGUgT09CIHNldCwgd2hlcmUgdGhlIHByZWRpY3Rpb24gaXMgb2J0YWluZWQgYnkgYXZlcmFnaW5nIHRoZSByZXNwb25zZSAoaW4gcmVncmVzc2lvbikgb3IgYXMgYSBtYWpvcml0eSB2b3RlIChpbiBjbGFzc2lmaWNhdGlvbikgZnJvbSBhbGwgdGhlIHRyZWVzIGluIHRoZSBmb3Jlc3QgdGhhdCB3ZXJlIG5vdCB0cmFpbmVkIG9uIHRoYXQgcGFydGljdWxhciBPT0IgaW5zdGFuY2UuDQoNCi0gKipUaGUgUmFuZG9tIFN1YnNwYWNlIE1ldGhvZCAoRmVhdHVyZSBCYWdnaW5nKS4qKiBUaGUgUmFuZG9tIFN1YnNwYWNlIE1ldGhvZCBpcyBhIG1ldGhvZCB0byBjb250cm9sIGZvciB0aGUgY29tcGxleGl0eSBvZiB0aGUgZGVjaXNpb24gdHJlZXMgZ3Jvd24gaW4gYSBSYW5kb20gRm9yZXN0IG1vZGVsLiAqKk9uIGVhY2ggbmV3IHNwbGl0KiosIG9ubHkgYSByYW5kb21seSBjaG9zZW4gKnN1YnNldCBvZiBwcmVkaWN0b3JzKiBpcyB1c2VkIHRvIGZpbmQgdGhlIG9wdGltYWwgc3BsaXQuIFRoZSBSYW5kb20gRm9yZXN0cyBhbGdvcml0aG0sIGFzIHdlIHdpbGwgc2VlLCBoYXMgYSBjb250cm9sIHBhcmFtZXRlciB0aGF0IGRldGVybWluZXMgaG93IG1hbnkgZmVhdHVyZXMgYXJlIHJhbmRvbWx5IHNlbGVjdGVkIHRvIHByb2R1Y2UgYSBuZXcgc3BsaXQuICANCg0KDQojIyMjIDEuMiBDbGFzc2lmaWNhdGlvbiB3LiB7cmFuZG9tRm9yZXN0fQ0KDQpXZSB3aWxsIGZpdCBhIFJhbmRvbSBGb3Jlc3QgbW9kZWwgdG8gdGhlIGBIUl9jb21tYV9zZXAuY3N2YCBkYXRhc2V0IHdpdGggYHJhbmRvbUZvcmVzdDo6cmFuZG9tRm9yZXN0KClgIGluIFIuIEluIHNwaXRlIG9mIGFsbCB0aGUgcHJlY2F1dGlvbmFyeSBtZWFzdXJlcyBhbHJlYWR5IHRha2VuIGluIHRoZSBSYW5kb20gRm9yZXN0IG1vZGVsIGl0c2VsZiwgd2Ugd2lsbCBzdGlsbCBwZXJmb3JtIGFuIGFkZGl0aW9uYWwgKm91dHRlciogay1mb2xkIGNyb3NzLXZhbGlkYXRpb24gd2l0aCA1IGZvbGRzOiBiZXR0ZXIgc2FmZSB0aGFuIHNvcnJ5LiANCg0KRmlyc3QsIGRlZmluZSB0aGUgZm9sZHM6DQoNCmBgYHtyIGVjaG8gPSBULCBtZXNzYWdlID0gRiwgd2FybmluZyA9IEZ9DQpkYXRhU2V0JGl4IDwtIHNhbXBsZSgxOjUsIGRpbShkYXRhU2V0KVsxXSwgcmVwbGFjZSA9IFQpDQp0YWJsZShkYXRhU2V0JGl4KQ0KYGBgDQpQZXJmb3JtIGEgNS1mb2xkIGNyb3NzIHZhbGlkYXRpb24gZm9yIGEgc2V0IG9mIFJhbmRvbSBGb3Jlc3RzIGFjcm9zcyB0aGUgZm9sbG93aW5nIGNvbnRyb2wgcGFyYW1ldGVyczoNCg0KLSAqKm50cmVlOioqIHRoZSBudW1iZXIgb2YgdHJlZXMgdG8gZ3Jvdw0KLSAqKm10cnk6KiogdGhlIG51bWJlciBvZiB2YXJpYWJsZXMgdG8gcmFuZG9tbHkgc2FtcGxlIGFzIGNhbmRpZGF0ZXMgYXQgZWFjaCBzcGxpdCAodG8gY29udHJvbCBGZWF0dXJlIEJhZ2dpbmcpDQoNCmBgYHtyIGVjaG8gPSBULCBtZXNzYWdlID0gRiwgd2FybmluZyA9IEZ9DQpudHJlZSA8LSBzZXEoMjUwLCAxMDAwLCBieSA9IDI1MCkNCm10cnkgPC0gMTooZGltKGRhdGFTZXQpWzJdLTIpDQojIC0gbXRyeTogd2UgZG8gbm90IGNvdW50IGBsZWZ0YCB3aGljaCBpcyBhbiBvdXRjb21lDQojIC0gYW5kIGBpeGAgd2hpY2ggaXMgYSBmb2xkIGluZGV4LCBzbyB3ZSBoYXZlDQojIC0gZGltKGRhdGFTZXQpWzJdLTIgcHJlZGljdG9ycyBpbiB0aGUgbW9kZWwuDQojIC0gc3RhcnQgdGltZXI6DQp0c3RhcnQgPC0gU3lzLnRpbWUoKQ0KcmZNb2RlbHMgPC0gbGFwcGx5KG50cmVlLCBmdW5jdGlvbihudCkgew0KICAjIC0gbGFwcGx5KCkgYWNyb3NzIG50cmVlDQogIG10cnljdiA8LSBsYXBwbHkobXRyeSwgZnVuY3Rpb24obXQpIHsNCiAgICAjIC0gbGFwcGx5KCkgYWNyb3NzIG10DQogICAgY3YgPC0gbGFwcGx5KHVuaXF1ZShkYXRhU2V0JGl4KSwgZnVuY3Rpb24oZm9sZCkgew0KICAgICAgIyAtIGxhcHBseSBhY3Jvc3MgZm9sZHM6DQogICAgICAjIC0gc3BsaXQgdHJhaW5pbmcgYW5kIHRlc3Qgc2V0cw0KICAgICAgdGVzdEl4IDwtIGZvbGQNCiAgICAgIHRyYWluSXggPC0gc2V0ZGlmZigxOjUsIHRlc3RJeCkNCiAgICAgIHRyYWluU2V0IDwtIGRhdGFTZXQgJT4lIA0KICAgICAgICBkcGx5cjo6ZmlsdGVyKGl4ICVpbiUgdHJhaW5JeCkgJT4lIA0KICAgICAgICBkcGx5cjo6c2VsZWN0KC1peCkNCiAgICAgIHRlc3RTZXQgPC0gZGF0YVNldCAlPiUgDQogICAgICAgIGRwbHlyOjpmaWx0ZXIoaXggJWluJSB0ZXN0SXgpICU+JQ0KICAgICAgICBkcGx5cjo6c2VsZWN0KC1peCkNCiAgICAgICMgLSBgbGVmdGAgdG8gZmFjdG9yIGZvciBjbGFzc2lmaWNhdGlvbiANCiAgICAgICMgLSAgdy4gcmFuZG9tRm9yZXN0KCkNCiAgICAgIHRyYWluU2V0JGxlZnQgPC0gYXMuZmFjdG9yKHRyYWluU2V0JGxlZnQpDQogICAgICB0ZXN0U2V0JGxlZnQgPC0gYXMuZmFjdG9yKHRlc3RTZXQkbGVmdCkNCiAgICAgICMgLSBSYW5kb20gRm9yZXN0Og0KICAgICAgbW9kZWwgPC0gcmFuZG9tRm9yZXN0OjpyYW5kb21Gb3Jlc3QoZm9ybXVsYSA9IGxlZnQgfiAuLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGF0YSA9IHRyYWluU2V0LCANCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG50cmVlID0gbnQsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtdHJ5ID0gbXQNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICkNCiAgICAgICMgLSBST0MgYW5hbHlzaXM6DQogICAgICBwcmVkaWN0aW9ucyA8LSBwcmVkaWN0KG1vZGVsLCANCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbmV3ZGF0YSA9IHRlc3RTZXQpDQogICAgICBoaXQgPC0gc3VtKGlmZWxzZShwcmVkaWN0aW9ucyA9PSAxICYgdGVzdFNldCRsZWZ0ID09IDEsIDEsIDApKQ0KICAgICAgaGl0IDwtIGhpdC9zdW0odGVzdFNldCRsZWZ0ID09IDEpDQogICAgICBmYSA8LSBzdW0oaWZlbHNlKHByZWRpY3Rpb25zID09IDEgJiB0ZXN0U2V0JGxlZnQgPT0gMCwgMSwgMCkpDQogICAgICBmYSA8LSBmYS9zdW0odGVzdFNldCRsZWZ0ID09IDApDQogICAgICBhY2MgPC0gc3VtKHByZWRpY3Rpb25zID09IHRlc3RTZXQkbGVmdCkNCiAgICAgIGFjYyA8LSBhY2MvbGVuZ3RoKHRlc3RTZXQkbGVmdCkNCiAgICAgICMgLSBPdXRwdXQ6DQogICAgICByZXR1cm4oDQogICAgICAgIGRhdGEuZnJhbWUoZm9sZCwgaGl0LCBmYSwgYWNjKQ0KICAgICAgKQ0KICAgIH0pDQogICAgIyAtIGNvbGxlY3QgcmVzdWx0cyBmcm9tIGFsbCBmb2xkczoNCiAgICBjdiA8LSByYmluZGxpc3QoY3YpDQogICAgIyAtIGF2ZXJhZ2UgUk9DOg0KICAgIGF2Z19yb2MgPC0gZGF0YS5mcmFtZShoaXQgPSBtZWFuKGN2JGhpdCksDQogICAgICAgICAgICAgICAgICAgICAgICAgIGZhID0gbWVhbihjdiRmYSksIA0KICAgICAgICAgICAgICAgICAgICAgICAgICBhY2MgPSBtZWFuKGN2JGFjYyksDQogICAgICAgICAgICAgICAgICAgICAgICAgIG10cnkgPSBtdCkNCiAgICByZXR1cm4oYXZnX3JvYykNCiAgfSkNCiAgIyAtIGNvbGxlY3QgZnJvbSBhbGwgbXRyeSB2YWx1ZXM6DQogIG10cnljdiA8LSByYmluZGxpc3QobXRyeWN2KQ0KICAjIC0gYWRkIG50cmVlIGFuZCBvdXQ6DQogIG10cnljdiRudHJlZSA8LSBudA0KICByZXR1cm4obXRyeWN2KQ0KfSkNCiMgLSBjb2xsZWN0IGFsbCByZXN1bHRzDQpyZk1vZGVscyA8LSByYmluZGxpc3QocmZNb2RlbHMpDQp3cml0ZS5jc3YocmZNb2RlbHMsIA0KICAgICAgICAgIHBhc3RlMChnZXR3ZCgpLCAiL3JmTW9kZWxzLmNzdiIpKQ0KIyAtIFJlcG9ydCB0aW1pbmc6DQpwcmludChwYXN0ZTAoIlRoZSBlc3RpbWF0aW9uIHRvb2s6ICIsIA0KICAgICAgICAgICAgIGRpZmZ0aW1lKFN5cy50aW1lKCksIHRzdGFydCwgdW5pdHMgPSAibWlucyIpLCANCiAgICAgICAgICAgICAiIG1pbnV0ZXMuIikpDQpgYGANCg0KYGBge3IgZWNobyA9IFQsIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0NCnByaW50KHJmTW9kZWxzKQ0KYGBgDQoNCkxldCdzIGluc3BlY3QgdGhlIENWIHJlc3VsdHMgdmlzdWFsbHkuIEFjY3VyYWN5IGZpcnN0Og0KDQpgYGB7ciBlY2hvID0gVCwgbWVzc2FnZSA9IEYsIHdhcm5pbmcgPSBGfQ0KcmZNb2RlbHMkbnRyZWUgPC0gZmFjdG9yKHJmTW9kZWxzJG50cmVlKQ0KcmZNb2RlbHMkbXRyeSA8LSBmYWN0b3IocmZNb2RlbHMkbXRyeSkNCmdncGxvdChkYXRhID0gcmZNb2RlbHMsIA0KICAgICAgIGFlcyh4ID0gbXRyeSwNCiAgICAgICAgICAgeSA9IGFjYywgDQogICAgICAgICAgIGdyb3VwID0gbnRyZWUsIA0KICAgICAgICAgICBjb2xvciA9IG50cmVlLA0KICAgICAgICAgICBmaWxsID0gbnRyZWUsDQogICAgICAgICAgIGxhYmVsID0gcm91bmQoYWNjLCAyKSkNCiAgICAgICApICsNCiAgZ2VvbV9wYXRoKHNpemUgPSAuMjUpICsgDQogIGdlb21fcG9pbnQoc2l6ZSA9IDEuNSkgKyANCiAgZ2d0aXRsZSgiUmFuZG9tIEZvcmVzdHMgQ1Y6IEFjY3VyYWN5IikgKw0KICB0aGVtZV9idygpICsgDQogIHRoZW1lKHBhbmVsLmJvcmRlciA9IGVsZW1lbnRfYmxhbmsoKSkgKw0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gLjUsIHNpemUgPSA4KSkNCmBgYA0KDQpIaXQgcmF0ZToNCg0KYGBge3IgZWNobyA9IFQsIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0NCmdncGxvdChkYXRhID0gcmZNb2RlbHMsIA0KICAgICAgIGFlcyh4ID0gbXRyeSwNCiAgICAgICAgICAgeSA9IGhpdCwgDQogICAgICAgICAgIGdyb3VwID0gbnRyZWUsIA0KICAgICAgICAgICBjb2xvciA9IG50cmVlLA0KICAgICAgICAgICBmaWxsID0gbnRyZWUsDQogICAgICAgICAgIGxhYmVsID0gcm91bmQoYWNjLCAyKSkNCiAgICAgICApICsNCiAgZ2VvbV9wYXRoKHNpemUgPSAuMjUpICsgDQogIGdlb21fcG9pbnQoc2l6ZSA9IDEuNSkgKyANCiAgZ2d0aXRsZSgiUmFuZG9tIEZvcmVzdHMgQ1Y6IEhpdCBSYXRlIikgKw0KICB0aGVtZV9idygpICsgDQogIHRoZW1lKHBhbmVsLmJvcmRlciA9IGVsZW1lbnRfYmxhbmsoKSkgKw0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gLjUsIHNpemUgPSA4KSkNCmBgYA0KRmFsc2UgQWxhcm0gcmF0ZToNCg0KYGBge3IgZWNobyA9IFQsIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0NCmdncGxvdChkYXRhID0gcmZNb2RlbHMsIA0KICAgICAgIGFlcyh4ID0gbXRyeSwNCiAgICAgICAgICAgeSA9IGZhLCANCiAgICAgICAgICAgZ3JvdXAgPSBudHJlZSwgDQogICAgICAgICAgIGNvbG9yID0gbnRyZWUsDQogICAgICAgICAgIGZpbGwgPSBudHJlZSwNCiAgICAgICAgICAgbGFiZWwgPSByb3VuZChhY2MsIDIpKQ0KICAgICAgICkgKw0KICBnZW9tX3BhdGgoc2l6ZSA9IC4yNSkgKyANCiAgZ2VvbV9wb2ludChzaXplID0gMS41KSArIA0KICBnZ3RpdGxlKCJSYW5kb20gRm9yZXN0cyBDVjogRkEgUmF0ZSIpICsNCiAgdGhlbWVfYncoKSArIA0KICB0aGVtZShwYW5lbC5ib3JkZXIgPSBlbGVtZW50X2JsYW5rKCkpICsNCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IC41LCBzaXplID0gOCkpDQpgYGANCg0KQW5kIHBpY2sgdGhlIGJlc3QgbW9kZWwgZnJvbSBST0M6DQoNCmBgYHtyIGVjaG8gPSBULCBtZXNzYWdlID0gRiwgd2FybmluZyA9IEZ9DQpyZk1vZGVscyRkaWZmIDwtIHJmTW9kZWxzJGhpdCAtIHJmTW9kZWxzJGZhDQp3X2Jlc3QgPC0gd2hpY2gubWF4KHJmTW9kZWxzJGRpZmYpDQpyZk1vZGVsc1t3X2Jlc3QsIF0NCmBgYA0KDQpBbmQgd2UgY2FuIHN0aWxsIHJlZmluZSB0aGUgY2hvc2VuIG1vZGVsOg0KDQpgYGB7ciBlY2hvID0gVCwgbWVzc2FnZSA9IEYsIHdhcm5pbmcgPSBGfQ0KZGF0YVNldCA8LSBkYXRhU2V0ICU+JSANCiAgZHBseXI6OnNlbGVjdCgtaXgpDQpkYXRhU2V0JGxlZnQgPC0gZmFjdG9yKGRhdGFTZXQkbGVmdCkNCm9wdGltYWxfbW9kZWwgPC0gcmFuZG9tRm9yZXN0OjpyYW5kb21Gb3Jlc3QoZm9ybXVsYSA9IGxlZnQgfiAuLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkYXRhID0gZGF0YVNldCwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbnRyZWUgPSAyNTAsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG10cnkgPSA0KQ0Kb3B0aW1hbF9tb2RlbCRpbXBvcnRhbmNlDQpgYGANCg0KVGhlIGN1bXVsYXRpdmUgT09CIGVycm9yIHVwIHRvIHRoZSBpLXRoIHRyZWUgY2FuIGJlIGZvdW5kIGluIHRoZSBmaXJzdCBjb2x1bW4gb2YgdGhlIGBvcHRpbWFsX21vZGVsJGVyci5yYXRlYCBmaWVsZDoNCg0KYGBge3IgZWNobyA9IFQsIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0NCmhlYWQob3B0aW1hbF9tb2RlbCRlcnIucmF0ZSkNCmBgYA0KTGV0J3MgdGFrZSBhIGNsb3NlciBsb29rIGF0IGl0Og0KDQpgYGB7ciBlY2hvID0gVCwgbWVzc2FnZSA9IEYsIHdhcm5pbmcgPSBGfQ0Kb29iRnJhbWUgPC0gYXMuZGF0YS5mcmFtZShvcHRpbWFsX21vZGVsJGVyci5yYXRlKQ0Kb29iRnJhbWUkbnRyZWUgPC0gMTpkaW0ob29iRnJhbWVbMV0pDQpnZ3Bsb3QoZGF0YSA9IG9vYkZyYW1lLCANCiAgICAgICBhZXMoeCA9IG50cmVlLA0KICAgICAgICAgICB5ID0gT09CKSkgKyANCiAgZ2VvbV9wYXRoKHNpemUgPSAuMjUpICsgDQogIGdlb21fcG9pbnQoc2l6ZSA9IDEuNSkgKyANCiAgZ2d0aXRsZSgiQ3VtdWxhdGl2ZSBPT0IgZXJyb3IgZnJvbSB0aGUgQ1Ygb3B0aW1hbCBSYW5kb20gRm9yZXN0IG1vZGVsIikgKw0KICB0aGVtZV9idygpICsgDQogIHRoZW1lKHBhbmVsLmJvcmRlciA9IGVsZW1lbnRfYmxhbmsoKSkgKw0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gLjUsIHNpemUgPSA4KSkNCmBgYA0KDQpXZSBjYW4gb2JzZXJ2ZSBob3cgdGhlIGN1bXVsYXRpdmUgT09CIGVycm9yIHN0YWJpbGl6ZXMgZm9sbG93aW5nIHRoZSBncm93dGggb2YgYSBjZXJ0YWluIG51bWJlciBvZiB0cmVlcyBpbiB0aGUgUmFuZG9tIEZvcmVzdCBtb2RlbDoNCg0KYGBge3IgZWNobyA9IFQsIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0NCndfdHJlZSA8LSB3aGljaC5taW4ob29iRnJhbWUkT09CKQ0KcHJpbnQod190cmVlKQ0KYGBgDQpBbmQgZmluYWxseToNCg0KYGBge3IgZWNobyA9IFQsIG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRn0NCm9wdGltYWxfbW9kZWwgPC0gcmFuZG9tRm9yZXN0OjpyYW5kb21Gb3Jlc3QoZm9ybXVsYSA9IGxlZnQgfiAuLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkYXRhID0gZGF0YVNldCwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbnRyZWUgPSB3X3RyZWUsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG10cnkgPSA0DQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICkNCnByZWRpY3Rpb25zIDwtIHByZWRpY3Qob3B0aW1hbF9tb2RlbCwgDQogICAgICAgICAgICAgICAgICAgICAgIG5ld2RhdGEgPSBkYXRhU2V0KQ0KaGl0IDwtIHN1bShpZmVsc2UocHJlZGljdGlvbnMgPT0gMSAmIGRhdGFTZXQkbGVmdCA9PSAxLCAxLCAwKSkNCmhpdCA8LSBoaXQvc3VtKGRhdGFTZXQkbGVmdCA9PSAxKQ0KZmEgPC0gc3VtKGlmZWxzZShwcmVkaWN0aW9ucyA9PSAxICYgZGF0YVNldCRsZWZ0ID09IDAsIDEsIDApKQ0KZmEgPC0gZmEvc3VtKGRhdGFTZXQkbGVmdCA9PSAwKQ0KYWNjIDwtIHN1bShwcmVkaWN0aW9ucyA9PSBkYXRhU2V0JGxlZnQpDQphY2MgPC0gYWNjL2xlbmd0aChkYXRhU2V0JGxlZnQpDQpwcmludChwYXN0ZTAoIkFjY3VyYWN5OiAiLCBhY2MsICI7IEhpdCByYXRlOiAiLCBoaXQsICI7IEZBIHJhdGU6ICIsIGZhKSkNCmBgYA0KDQojIyMgMi4gUmFuZG9tIEZvcmVzdHMgZm9yIFJlZ3Jlc3Npb24NCg0KSW4ge3JhbmRvbUZvcmVzdH0sIHRvIG9idGFpbiB0aGUgUmFuZG9tIEZvcmVzdCBtb2RlbCBmb3IgcmVncmVzc2lvbiAqKnNpbXBseSBkbyBub3QgcHJvbm91bmNlIGFuIG91dGNvbWUgdG8gYmUgYSBmYWN0b3IqKi4NCldlIHdpbGwgdXNlIHRoZSBCb3N0b24gSG91c2luZyBkYXRhc2V0IHRvIGRlbW9uc3RyYXRlLg0KDQpgYGB7ciBlY2hvID0gVCwgbWVzc2FnZSA9IEYsIHdhcm5pbmcgPSBGfQ0KZGF0YVNldCA8LSByZWFkLmNzdihwYXN0ZTAoJ19kYXRhLycsICdCb3N0b25Ib3VzaW5nLmNzdicpLCANCiAgICAgICAgICAgICAgICAgICAgaGVhZGVyID0gVCwgDQogICAgICAgICAgICAgICAgICAgIGNoZWNrLm5hbWVzID0gRiwNCiAgICAgICAgICAgICAgICAgICAgc3RyaW5nc0FzRmFjdG9ycyA9IEYpDQpoZWFkKGRhdGFTZXQpDQpgYGANCg0KSGVyZSBhcmUgdGhlIHZhcmlhYmxlczoNCg0KKyAqKmNyaW0qKjogcGVyIGNhcGl0YSBjcmltZSByYXRlIGJ5IHRvd24NCisgKip6bioqOiBwcm9wb3J0aW9uIG9mIHJlc2lkZW50aWFsIGxhbmQgem9uZWQgZm9yIGxvdHMgb3ZlciAyNSwwMDAgc3EuZnQuDQorICoqaW5kdXMqKjogcHJvcG9ydGlvbiBvZiBub24tcmV0YWlsIGJ1c2luZXNzIGFjcmVzIHBlciB0b3duLg0KKyAqKmNoYXMqKjogQ2hhcmxlcyBSaXZlciBkdW1teSB2YXJpYWJsZSAoMSBpZiB0cmFjdCBib3VuZHMgcml2ZXI7IDAgb3RoZXJ3aXNlKQ0KKyAqKm5veCoqOiBuaXRyaWMgb3hpZGVzIGNvbmNlbnRyYXRpb24gKHBhcnRzIHBlciAxMCBtaWxsaW9uKQ0KKyAqKnJtKio6IGF2ZXJhZ2UgbnVtYmVyIG9mIHJvb21zIHBlciBkd2VsbGluZw0KKyAqKmFnZSoqOiBwcm9wb3J0aW9uIG9mIG93bmVyLW9jY3VwaWVkIHVuaXRzIGJ1aWx0IHByaW9yIHRvIDE5NDANCisgKipkaXMqKjogd2VpZ2h0ZWQgZGlzdGFuY2VzIHRvIGZpdmUgQm9zdG9uIGVtcGxveW1lbnQgY2VudGVycw0KKyAqKnJhZCoqOiBpbmRleCBvZiBhY2Nlc3NpYmlsaXR5IHRvIHJhZGlhbCBoaWdod2F5cw0KKyAqKnRheCoqOiBmdWxsLXZhbHVlIHByb3BlcnR5LXRheCByYXRlIHBlciAkMTAsMDAwDQorICoqcHRyYXRpbyoqOiBwdXBpbC10ZWFjaGVyIHJhdGlvIGJ5IHRvd24NCisgKipiKio6IDEwMDAoQmsgLSAwLjYzKV4yIHdoZXJlIEJrIGlzIHRoZSBwcm9wb3J0aW9uIG9mIGJsYWNrcyBieSB0b3duDQorICoqbHN0YXQqKjogJSBsb3dlciBzdGF0dXMgb2YgdGhlIHBvcHVsYXRpb24NCisgKiptZWR2Kio6IE1lZGlhbiB2YWx1ZSBvZiBvd25lci1vY2N1cGllZCBob21lcyBpbiAkMTAwMCdzDQoNClRoZSBgbWVkdmAgdmFyaWFibGUgaXMgdGhlICpvdXRjb21lKi4NCg0KUmFuZG9tIEZvcmVzdCAobm8gY3Jvc3MtdmFsaWRhdGlvbiB0aGlzIHRpbWUpOg0KDQpgYGB7ciBlY2hvID0gVCwgbWVzc2FnZSA9IEYsIHdhcm5pbmcgPSBGfQ0KcmZSZWdNc29kZWwgPC0gcmFuZG9tRm9yZXN0OjpyYW5kb21Gb3Jlc3QoZm9ybXVsYSA9IG1lZHYgfiAuLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGF0YSA9IGRhdGFTZXQsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBudHJlZSA9IDEwMDAsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtdHJ5ID0gNw0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKQ0KYGBgDQoNCldlIGNhbiB1c2UgdGhlIGdlbmVyaWMgYHBsb3QoKWAgZnVuY3Rpb24gdG8gYXNzZXNzIGhvdyB0aGUgTVNFIGNoYW5nZXMgYWNyb3NzIGBudHJlZWA6DQoNCmBgYHtyIGVjaG8gPSBULCBtZXNzYWdlID0gRiwgd2FybmluZyA9IEZ9DQpwbG90KHJmUmVnTXNvZGVsKQ0KYGBgDQoNCmBgYHtyIGVjaG8gPSBULCBtZXNzYWdlID0gRiwgd2FybmluZyA9IEZ9DQpwcmVkaWN0aW9ucyA8LSBwcmVkaWN0KHJmUmVnTXNvZGVsLCANCiAgICAgICAgICAgICAgICAgICAgICAgbmV3ZGF0YSA9IGRhdGFTZXQpDQpwcmVkaWN0RnJhbWUgPC0gZGF0YS5mcmFtZShwcmVkaWN0ZWRfbWVkdiA9IHByZWRpY3Rpb25zLCANCiAgICAgICAgICAgICAgICAgICAgICAgICAgIG9ic2VydmVkX21lZHYgPSBkYXRhU2V0JG1lZHYpDQpnZ3Bsb3QoZGF0YSA9IHByZWRpY3RGcmFtZSwgDQogICAgICAgYWVzKHggPSBwcmVkaWN0ZWRfbWVkdiwNCiAgICAgICAgICAgeSA9IG9ic2VydmVkX21lZHYpKSArIA0KICBnZW9tX3Ntb290aChtZXRob2QgPSAibG0iLCBzaXplID0gLjI1LCBjb2xvciA9ICJyZWQiKSArIA0KICBnZW9tX3BvaW50KHNpemUgPSAxLjUsIGNvbG9yID0gImJsYWNrIikgKyANCiAgZ2VvbV9wb2ludChzaXplID0gLjc1LCBjb2xvciA9ICJ3aGl0ZSIpICsNCiAgZ2d0aXRsZSgiUmFuZG9tIEZvcmVzdCBpbiBSZWdyZXNzaW9uOiBPYnNlcnZlZCB2cyBQcmVkaWN0ZWRcbkJvc3RvbiBIb3VzaW5nIERhdGFzZXQiKSArIA0KICB0aGVtZV9idygpICsgDQogIHRoZW1lKHBhbmVsLmJvcmRlciA9IGVsZW1lbnRfYmxhbmsoKSkgKw0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gLjUsIHNpemUgPSA4KSkNCmBgYA0KDQoqKioNCg0KIyMjIEZ1cnRoZXIgUmVhZGluZ3MNCg0KKyBbQmFnZ2luZyAoQm9vdHN0cmFwIEFnZ3JlZ2F0aW9uKSwgZnJvbSBDb3Jwb3JhdGUgRmluYW5jZSBJbnN0aXR1dGVdKGh0dHBzOi8vY29ycG9yYXRlZmluYW5jZWluc3RpdHV0ZS5jb20vcmVzb3VyY2VzL2tub3dsZWRnZS9vdGhlci9iYWdnaW5nLWJvb3RzdHJhcC1hZ2dyZWdhdGlvbi8pDQoNCisgW0hhbmRzLU9uIE1hY2hpbmUgTGVhcm5pbmcgd2l0aCBSLCBDaGFwdGVyIDEwIEJhZ2dpbmddKGh0dHBzOi8vYnJhZGxleWJvZWhta2UuZ2l0aHViLmlvL0hPTUwvYmFnZ2luZy5odG1sKQ0KDQorIFtBIHZlcnkgYmFzaWMgaW50cm9kdWN0aW9uIHRvIFJhbmRvbSBGb3Jlc3RzIHVzaW5nIFIsIGZyb20gT3hmb3JkIFByb3RlaW4gSW5mb3JtYXRpY3MgR3JvdXBdKGh0dHBzOi8vd3d3LmJsb3BpZy5jb20vYmxvZy8yMDE3LzA0L2EtdmVyeS1iYXNpYy1pbnRyb2R1Y3Rpb24tdG8tcmFuZG9tLWZvcmVzdHMtdXNpbmctci8pDQoNCisgW0EgZ2VudGxlIGludHJvZHVjdGlvbiB0byByYW5kb20gZm9yZXN0cyB1c2luZyBSLCBFaWdodCB0byBMYXRlXShodHRwczovL2VpZ2h0MmxhdGUud29yZHByZXNzLmNvbS8yMDE2LzA5LzIwL2EtZ2VudGxlLWludHJvZHVjdGlvbi10by1yYW5kb20tZm9yZXN0cy11c2luZy1yLykNCg0KKyBbVklERU8gUmFuZG9tIEZvcmVzdCBJbiBSIHwgU2ltcGxpbGVhcm5dKGh0dHBzOi8vd3d3LnlvdXR1YmUuY29tL3dhdGNoP3Y9SGVUVDczV3hLSWMpDQoNCisgW1VuZGVyc3RhbmRpbmcgUmFuZG9tIEZvcmVzdDogSG93IHRoZSBBbGdvcml0aG0gV29ya3MgYW5kIFdoeSBpdCBJcyBTbyBFZmZlY3RpdmUsIFRvbnkgWWl1LCBUb3dhcmRzIERhdGEgU2NpZW5jZSwgTWVkaXVtXShodHRwczovL3Rvd2FyZHNkYXRhc2NpZW5jZS5jb20vdW5kZXJzdGFuZGluZy1yYW5kb20tZm9yZXN0LTU4MzgxZTA2MDJkMiNfPV8pDQoNCg0KDQoqKioNCkdvcmFuIFMuIE1pbG92YW5vdmnEhw0KDQpEYXRhS29sZWt0aXYsIDIwMjAvMjENCg0KY29udGFjdDogZ29yYW4ubWlsb3Zhbm92aWNAZGF0YWtvbGVrdGl2LmNvbQ0KDQohW10oLi4vX2ltZy9ES19Mb2dvXzEwMC5wbmcpDQoNCioqKg0KTGljZW5zZTogW0dQTHYzXShodHRwOi8vd3d3LmdudS5vcmcvbGljZW5zZXMvZ3BsLTMuMC50eHQpDQpUaGlzIE5vdGVib29rIGlzIGZyZWUgc29mdHdhcmU6IHlvdSBjYW4gcmVkaXN0cmlidXRlIGl0IGFuZC9vciBtb2RpZnkgaXQgdW5kZXIgdGhlIHRlcm1zIG9mIHRoZSBHTlUgR2VuZXJhbCBQdWJsaWMgTGljZW5zZSBhcyBwdWJsaXNoZWQgYnkgdGhlIEZyZWUgU29mdHdhcmUgRm91bmRhdGlvbiwgZWl0aGVyIHZlcnNpb24gMyBvZiB0aGUgTGljZW5zZSwgb3IgKGF0IHlvdXIgb3B0aW9uKSBhbnkgbGF0ZXIgdmVyc2lvbi4NClRoaXMgTm90ZWJvb2sgaXMgZGlzdHJpYnV0ZWQgaW4gdGhlIGhvcGUgdGhhdCBpdCB3aWxsIGJlIHVzZWZ1bCwgYnV0IFdJVEhPVVQgQU5ZIFdBUlJBTlRZOyB3aXRob3V0IGV2ZW4gdGhlIGltcGxpZWQgd2FycmFudHkgb2YgTUVSQ0hBTlRBQklMSVRZIG9yIEZJVE5FU1MgRk9SIEEgUEFSVElDVUxBUiBQVVJQT1NFLiAgU2VlIHRoZSBHTlUgR2VuZXJhbCBQdWJsaWMgTGljZW5zZSBmb3IgbW9yZSBkZXRhaWxzLg0KWW91IHNob3VsZCBoYXZlIHJlY2VpdmVkIGEgY29weSBvZiB0aGUgR05VIEdlbmVyYWwgUHVibGljIExpY2Vuc2UgYWxvbmcgd2l0aCB0aGlzIE5vdGVib29rLiBJZiBub3QsIHNlZSA8aHR0cDovL3d3dy5nbnUub3JnL2xpY2Vuc2VzLz4uDQoNCioqKg0KDQo=